package tree;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//二叉树的层序遍历
public class leetcode102 {
    public static void main(String[] args) {
        Integer[] nums = {3,9,20,null,null,15,7};
        TreeNode root = createTree(nums);
        List<List<Integer>> result = levelOrder(root);
        for (List<Integer> integers : result) {
            System.out.println(integers);
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int n = 1;//记录当前层数
        while(!queue.isEmpty()){
            List<Integer> array = new ArrayList<>();
            int count = 0;
            for(int i = 0; i < n; i++){
                TreeNode temp =  queue.poll();
                array.add(temp.val);
                if(temp.left != null){
                    queue.offer(temp.left);
                    count++;
                }
                if(temp.right != null){
                    queue.offer(temp.right);
                    count++;
                }
            }
            n = count;
            result.add(array);
        }
        return result;
    }

    public static TreeNode createTree(Integer[] nums){
        if(nums == null || nums.length == 0) return null;

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while(!queue.isEmpty() && i < nums.length){
            TreeNode curr = queue.poll();

            if(i<nums.length && nums[i] != null){
                curr.left = new TreeNode(nums[i]);
                queue.offer(curr.left);
            }
            i++;
            if(i<nums.length && nums[i] != null){
                curr.right = new TreeNode(nums[i]);
                queue.offer(curr.right);
            }
            i++;
        }
        return root;
    }
}
